翻訳と辞書 Words near each other ・ Sum and Product Puzzle ・ Sum and Substance ・ Sum certain ・ Sum Elai-Mang ・ Sum frequency generation spectroscopy ・ Sum Mo Chikan ・ Sum of absolute differences ・ Sum of absolute transformed differences ・ Sum of angles of a triangle ・ Sum of Christianity ・ Sum of Logic ・ Sum of normally distributed random variables ・ Sum of Parts ・ Sum of perpetuities method ・ Sum of public power ・ Sum of radicals ・ Sum of squares ・ Sum of the Parts ・ Sum of two squares theorem ・ Sum Practysis of Medecyne and other Short Works ・ Sum rule ・ Sum rule in differentiation ・ Sum rule in integration ・ Sum rule in quantum mechanics ・ Sum to Infinity ・ Sum to Infinity (book) ・ Sum Ying Fung ・ Sum-free sequence ・ Sum-free set ・ Sum-frequency generation Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Sum of radicals ： ウィキペディア英語版 Sum of radicals In computational complexity theory there is an open problem whether some information about the sum of radicals may be computed in polynomial time depending on the input size, i.e., in the number of bits necessary to represent this sum. It is of importance for many problems in computational geometry, since the computation of the Euclidean distance between two points in general case involves the computation of a square root, and therefore the perimeter of a polygon or the length of a polygonal chain takes the form of a sum of radicals.〔Wolfgang Mulzer, Günter Rote, "Minimum-Weight Triangulation Is NP-Hard", In: Proceedings of the 22nd ''Annual Symposium on Computational Geometry'', Sedona, June 5–7, 2006, ''Journal of the ACM'', Vol. 55, No. 2, 2008.〕 The sum of radicals is defined as a finite linear combination of radicals: :$$ \Sigma_^n k_i \sqrt(), where $n,\; r\_i$ are natural numbers and $k\_i,\; x\_i$ are real numbers. Most theoretical research in computational geometry of combinatorial character assumes the computational model of infinite precision real RAM, i.e., an abstract computer in which real numbers and operations with them are performed with infinite precision and the input size of a real number and the cost of an elementary operation are constants. However there is research in computational complexity, especially in computer algebra, where the input size of a number is the number of bits necessary for its representation.〔''Computer Algebra Handbook'', 2003, ISBN 3-540-65466-6〕 In particular, of interest in computational geometry is the problem of determining the sign of the sum of radicals. For instance, the length of a polygonal path in which all vertices have integer coordinates may be expressed using the Pythagorean theorem as a sum of integer square roots, so in order to determine whether one path is longer or shorter than another in a Euclidean shortest path problem, it is necessary to determine the sign of an expression in which the first path's length is subtracted from the second; this expression is a sum of radicals. In a similar way, the sum of radicals problem is inherent in the problem of minimum-weight triangulation in the Euclidean metric. In 1991, Blömer proposed a polynomial time Monte Carlo algorithm for determining whether a sum of radicals is zero, or more generally whether it represents a rational number.〔.〕 While Blömer's result does not resolve the computational complexity of finding the sign of the sum of radicals, it does imply that if the latter problem is in class NP, then it is also in co-NP.〔 ==See also== *Nested radicals *Abel–Ruffini theorem 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sum of radicals」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.